package java_thinking.unit_17;

/**
 * @Desc:   数据结构：哈希 哈希函数 哈希表
 *          必看：https://blog.csdn.net/u011240877/article/details/52940469
 * @author: cww
 * @DateTime: 2019-04-14 10:28
 */

/**
 * 一、什么是 Hash
 *  1.Hash（哈希），又称“散列”，散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思；
 *    在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计
 *    算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。在介绍一些集合时，我们总强调需要重
 *    写某个类的 equals() 方法和 hashCode() 方法，确保唯一性。这里的 hashCode()表示的是对当前对象的唯一标示。计算
 *    hashCode 的过程就称作 哈希
 *    家里书一大堆，如果书存放时不分类直接摆到书架上（数组存储），找某本书时可能需要脑袋从左往右从上往下转好几圈才能
 *    发现；如果存放时按照类别分开放，技术书、小说、文学等等分开（按照某种哈希函数计算），找书时只要从它对应的分类里
 *    找，自然省事多了。
 *
 * 二、为什么要有 Hash
 *  1.我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的
 *  过程中，数组和链表都需要挨个循环比较，而通过 哈希 计算，可以大大减少比较次数
 *  2.案例，见上面链接
 *  3.因此可以发现，哈希 其实是随机存储的一种优化，先进行分类，然后查找时按照这个对象的分类去找
 *
 * 三、哈希函数
 *  1.哈希的过程中需要使用哈希函数进行计算。哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算
 *  出该元素存储位置的函数。表示为：address = H [key]
 *  2.几种常见的哈希函数（散列函数）构造方法：
 *      2.1.直接定址法：即 H(key) = key 或 H(key) = a*key + b，其中a和b为常数
 *      2.2.除留余数法: 取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址 即 H(key) = key % p, p < m
 *      2.3.数字分析法:当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址
 *          仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突
 *      2.4.平方取中法：先计算出关键字值的平方，然后取平方值中间几位作为散列地址
 *      2.5.折叠法(叠加法)：将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址
 *      2.6.随机数法:选择一个随机函数，把关键字的随机函数值作为它的哈希值,通常当关键字的长度不等时用这种方法
 *  3.构造哈希函数的方法很多，实际工作中要根据不同的情况选择合适的方法，总的原则是《尽可能少的产生冲突》通常考虑的因
 *  素有关键字的长度和分布情况、哈希值的范围等，如：当关键字是整数类型时就可以用除留余数法；如果关键字是小数类型，选
 *  择随机数法会比较好；
 *
 * 四、哈希冲突的解决
 *  1.选用哈希函数计算哈希值时，可能不同的 key 会得到相同的结果，一个地址怎么存放多个数据呢？这就是冲突;
 *  2.常用的主要有两种方法解决冲突:
 *      2.1.链接法(拉链法)：拉链法解决冲突的做法是--将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长
 *      度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1]，凡是散列地址为 i 的结点，均插入到以
 *      T[i] 为头指针的单链表中，T 中各分量的初值均应为空指针，在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。
 *      2.2.开放定址法:简单的说：当冲突发生时，使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址，只要散列表
 *      足够大，空的散列地址总能找到,按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列
 *      法等;
 *
 * 五、哈希的应用
 *  1.哈希表：哈希表是实现关联数组(associative array)的一种数据结构，广泛应用于实现数据的快速查找
 *          数组的特点是：寻址容易，插入和删除困难；
 *          而链表的特点是：寻址困难，插入和删除容易。
 *          哈希表就是一个综合的解决方案
 *          用哈希函数计算关键字的哈希值(hash value),然后就将该数字对数组长度进行取余，取余结果就当作数组的下标,通过
 *          哈希值这个索引就可以找到关键字的存储位置，即桶(bucket),这个映射函数叫做散列函数，存放记录的数组叫做 散列
 *          表
 *          查找过程中，关键字的比较次数，取决于产生冲突的多少,
 *          影响产生冲突多少有以下三个因素:
 *          1.哈希函数是否均匀+计算简单；
 *          2.处理冲突的方法；
 *          3.哈希表的加载因子。(HashMap 中的加载因子为 0.75，即四分之三)
 *
 *  2.分布式缓存:网络环境下的分布式缓存系统一般基于一致性哈希（Consistent hashing）。简单的说，一致性哈希将哈希值取
 *              值空间组织成一个虚拟的环，各个服务器与数据关键字K使用相同的哈希函数映射到这个环上，数据会存储在它顺
 *              时针“游走”遇到的第一个服务器。可以使每个服务器节点的负载相对均衡，很大程度上避免资源的浪费。在动态分
 *              布式缓存系统中，哈希算法的设计是关键点。使用分布更合理的算法可以使得多个服务节点间的负载相对均衡，可
 *              以很大程度上避免资源的浪费以及部分服务器过载。 使用带虚拟节点的一致性哈希算法，可以有效地降低服务硬
 *              件环境变化带来的数据迁移代价和风险，从而使分布式缓存系统更加高效稳定;
 *
 * 六、优缺点
 *  1.优点：不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1)的时间级。实际上，这只
 *          需要几条机器指令，如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无
 *          与伦比的；
 *  2.缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中
 *          将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。
 *
 * 七：问题实例(海量数据处理)
 *     我们知道hash 表在海量数据处理中有着广泛的应用，下面，请看另一道百度面试题：
 *     题目：海量日志数据，提取出某日访问百度次数最多的那个IP。
 *     方案：IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。
 */
public class WhatIsHash {
}
